package top.humbleyuan.dfs;

import top.humbleyuan.datastructure.tree.TreeNode;

/**
 * @Author HumbleYuan
 * @Date 2020/5/19 19:51
 * @Des 验证二叉搜索树
 * @pro 可以用迭代中序遍历实现
 */
public class LeetCode_98 {
    public static void main(String[] args) {
        TreeNode head = new TreeNode(2);
        head.formTree();

        // 有个上下限的问题：
        System.out.println(isValid(head, Long.MIN_VALUE, Long.MAX_VALUE));
    }

    // dfs
    public static boolean isValid(TreeNode root, long min, long max) {
        if(root == null) {
            return true;
        }

        if(root.val <= min || root.val >= max) {
            return false;
        }

        // 每次更新上下界
        // 左子树上界更新，下界不更新；右子树相反
        return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
    }
}
